home *** CD-ROM | disk | FTP | other *** search
/ Usenet 1993 July / InfoMagic USENET CD-ROM July 1993.ISO / sources / x / volume2 / x11.3 / patch3 < prev    next >
Encoding:
Text File  |  1988-12-12  |  28.4 KB  |  1,197 lines
  1. Path: uunet!wyse!mikew
  2. From: mikew@wyse.wyse.com (Mike Wexler)
  3. Newsgroups: comp.sources.x
  4. Subject: v02i043:  X11 Release 3, Patch3
  5. Message-ID: <1897@wyse.wyse.com>
  6. Date: 12 Dec 88 21:19:27 GMT
  7. Organization: Wyse Technology, San Jose
  8. Lines: 1186
  9. Approved: mikew@wyse.com
  10.  
  11. Submitted-by: Xstuff service <xstuff@EXPO.LCS.MIT.EDU>
  12. Posting-number: Volume 2, Issue 43
  13. Archive-name: x11.3/patch3
  14.  
  15.  
  16.  
  17. This patch optimizes some special cases in the mi arc code.  It
  18. affects only server/ddx/mi/miarc.c
  19.  
  20. Circular arcs are now computed specially with a direct equation, instead of
  21. using the more general elipse solution.
  22.  
  23. Memory allocation for span generation/merging was rewritten to reduce
  24. the number of small Xalloc calls.
  25.  
  26. Zero height/width arcs now use pGC->PolyFillRect instead of miSppFillPoly.
  27.  
  28. All of these changes are based on actual -pg style profiling results run on a
  29. Vaxstation 3200.
  30.  
  31. Circular arcs are now at least 20 times faster, Zero width/height arcs are
  32. at least 10 times faster on the 3200.  I expect more substantial changes on
  33. Suns which don't have floating point hardware, but have no data which
  34. demonstrates this.
  35.  
  36. *** /tmp/,RCSt1a15146    Fri Dec  9 13:27:24 1988
  37. --- server/ddx/mi/miarc.c    Fri Dec  9 13:26:39 1988
  38. ***************
  39. *** 21,27 ****
  40.   SOFTWARE.
  41.   
  42.   ******************************************************************/
  43. ! /* $XConsortium: miarc.c,v 1.63 88/10/23 17:07:31 keith Exp $ */
  44.   /* Author: Keith Packard */
  45.   
  46.   #include "X.h"
  47. --- 21,27 ----
  48.   SOFTWARE.
  49.   
  50.   ******************************************************************/
  51. ! /* $XConsortium: miarc.c,v 1.67 88/12/09 13:25:56 keith Exp $ */
  52.   /* Author: Keith Packard */
  53.   
  54.   #include "X.h"
  55. ***************
  56. *** 34,39 ****
  57. --- 34,63 ----
  58.   #include "mifpoly.h"
  59.   #include "mi.h"
  60.   
  61. + /*
  62. +  * some interesting sematic interpretation of the protocol:
  63. +  *
  64. +  * Self intersecting arcs (i.e. those spanning 360 degrees) 
  65. +  *  never join with other arcs, and are drawn without caps
  66. +  *  (unless on/off dashed, in which case each dash segment
  67. +  *  is capped, except when the last segment meets the
  68. +  *  first segment, when no caps are drawn)
  69. +  *
  70. +  * double dash arcs are drawn in two parts, first the
  71. +  *  odd dashes (drawn in background) then the even dashes
  72. +  *  (drawn in foreground).  This means that overlapping
  73. +  *  sections of foreground/background are drawn twice,
  74. +  *  first in background then in foreground.  The double-draw
  75. +  *  occurs even when the function uses the destination values
  76. +  *  (e.g. xor mode).  This is the same way the wide-line
  77. +  *  code works and should be "fixed".
  78. +  *
  79. +  * the wide arc code will never be "correct" -- the protocol
  80. +  *  document specifies exact pixelization which is impossible
  81. +  *  when calculating pixel positions with complicated floating-
  82. +  *  point expressions.
  83. +  */
  84. + 
  85.   extern double sqrt(), cos(), sin(), atan();
  86.   
  87.   /* these are from our <math.h>, but I'm told some systems don't have
  88. ***************
  89. *** 72,91 ****
  90.       SppPointRec    counterClock;
  91.   } miArcFaceRec, *miArcFacePtr;
  92.   
  93. - /*
  94. -  * This is an entire sequence of arcs, computed and categorized according
  95. -  * to operation.  miDashArcs generates either one or two of these.
  96. -  */
  97. - 
  98.   typedef struct _miArcData {
  99.       xArc        arc;
  100.       int        render;        /* non-zero means render after drawing */
  101.       int        join;        /* related join */
  102.       int        cap;        /* related cap */
  103.       miArcFaceRec    bounds[2];
  104.       double        x0, y0, x1, y1;
  105.   } miArcDataRec, *miArcDataPtr;
  106.   
  107.   typedef struct _miPolyArc {
  108.       int        narcs;
  109.       miArcDataPtr    arcs;
  110. --- 96,116 ----
  111.       SppPointRec    counterClock;
  112.   } miArcFaceRec, *miArcFacePtr;
  113.   
  114.   typedef struct _miArcData {
  115.       xArc        arc;
  116.       int        render;        /* non-zero means render after drawing */
  117.       int        join;        /* related join */
  118.       int        cap;        /* related cap */
  119. +     int        selfJoin;    /* final dash meets first dash */
  120.       miArcFaceRec    bounds[2];
  121.       double        x0, y0, x1, y1;
  122.   } miArcDataRec, *miArcDataPtr;
  123.   
  124. + /*
  125. +  * This is an entire sequence of arcs, computed and categorized according
  126. +  * to operation.  miDashArcs generates either one or two of these.
  127. +  */
  128. + 
  129.   typedef struct _miPolyArc {
  130.       int        narcs;
  131.       miArcDataPtr    arcs;
  132. ***************
  133. *** 185,190 ****
  134. --- 210,216 ----
  135.    * from the scratch drawable to pDraw. (See the wide line code for a
  136.    * fuller explanation of this.)
  137.    */
  138. + 
  139.   void
  140.   miPolyArc(pDraw, pGC, narcs, parcs)
  141.       DrawablePtr    pDraw;
  142. ***************
  143. *** 316,321 ****
  144. --- 342,353 ----
  145.                    &arcData->bounds[LEFT_END]);
  146.           if (polyArcs[iphase].arcs[i].render) {
  147.               fillSpans (pDrawTo, pGCTo);
  148. +             /*
  149. +              * don't cap self-joining arcs
  150. +              */
  151. +             if (polyArcs[iphase].arcs[i].selfJoin &&
  152. +                 cap[iphase] < polyArcs[iphase].arcs[i].cap)
  153. +                 cap[iphase]++;
  154.               while (cap[iphase] < polyArcs[iphase].arcs[i].cap) {
  155.               int    arcIndex, end;
  156.               miArcDataPtr    arcData0;
  157. ***************
  158. *** 874,879 ****
  159. --- 906,912 ----
  160.       xArc        xarc;
  161.       int        iphase, prevphase, joinphase;
  162.       int        arcsJoin;
  163. +     int        selfJoin;
  164.   
  165.       int        iDash, dashRemaining;
  166.       int        iDashStart, dashRemainingStart, iphaseStart;
  167. ***************
  168. *** 937,943 ****
  169.           j = i + 1;
  170.           if (j == narcs)
  171.               j = 0;
  172. !         if (!data[i].selfJoin && 
  173.                (UNEQUAL (data[i].x1, data[j].x0) ||
  174.                 UNEQUAL (data[i].y1, data[j].y0)))
  175.            {
  176. --- 970,976 ----
  177.           j = i + 1;
  178.           if (j == narcs)
  179.               j = 0;
  180. !         if (data[i].selfJoin || 
  181.                (UNEQUAL (data[i].x1, data[j].x0) ||
  182.                 UNEQUAL (data[i].y1, data[j].y0)))
  183.            {
  184. ***************
  185. *** 959,964 ****
  186. --- 992,1001 ----
  187.           if (nexti == narcs)
  188.               nexti = 0;
  189.           if (isDashed) {
  190. +             /*
  191. +              * compute each individual dash segment using the path
  192. +              * length function
  193. +              */
  194.               startAngle = parcs[i].angle1;
  195.               spanAngle = parcs[i].angle2;
  196.               if (spanAngle > FULLCIRCLE)
  197. ***************
  198. *** 972,977 ****
  199. --- 1009,1016 ----
  200.               endAngle = startAngle + spanAngle;
  201.               backwards = spanAngle < 0;
  202.               prevDashAngle = startAngle;
  203. +             selfJoin = data[i].selfJoin &&
  204. +                      (iphase == 0 || isDoubleDash);
  205.               while (prevDashAngle != endAngle) {
  206.                   dashAngle = computeAngleFromPath
  207.                            (prevDashAngle, endAngle,
  208. ***************
  209. *** 992,997 ****
  210. --- 1031,1039 ----
  211.                       xarc.angle2 = spanAngle;
  212.                       arc = addArc (&arcs[iphase].arcs, &arcs[iphase].narcs,
  213.                                &arcSize[iphase], xarc);
  214. +                     /*
  215. +                      * cap each end of an on/off dash
  216. +                      */
  217.                       if (!isDoubleDash) {
  218.                           if (prevDashAngle != startAngle) {
  219.                               addCap (&arcs[iphase].caps,
  220. ***************
  221. *** 1010,1015 ****
  222. --- 1052,1060 ----
  223.                       arc->cap = arcs[iphase].ncaps;
  224.                       arc->join = arcs[iphase].njoins;
  225.                       arc->render = 0;
  226. +                     arc->selfJoin = 0;
  227. +                     if (dashAngle == endAngle)
  228. +                         arc->selfJoin = selfJoin;
  229.                   }
  230.                   prevphase = iphase;
  231.                   if (dashRemaining <= 0) {
  232. ***************
  233. *** 1026,1031 ****
  234. --- 1071,1077 ----
  235.                          &arcSize[iphase], parcs[i]);
  236.               arc->join = arcs[iphase].njoins;
  237.               arc->cap = arcs[iphase].ncaps;
  238. +             arc->selfJoin = data[i].selfJoin;
  239.               prevphase = iphase;
  240.           }
  241.           if (prevphase == 0 || isDoubleDash)
  242. ***************
  243. *** 1042,1048 ****
  244.           }
  245.           arcsJoin = narcs > 1 && 
  246.                    ISEQUAL (data[i].x1, data[j].x0) &&
  247. !                 ISEQUAL (data[i].y1, data[j].y0);
  248.           if (arcsJoin)
  249.               arc->render = 0;
  250.           else
  251. --- 1088,1095 ----
  252.           }
  253.           arcsJoin = narcs > 1 && 
  254.                    ISEQUAL (data[i].x1, data[j].x0) &&
  255. !                 ISEQUAL (data[i].y1, data[j].y0) &&
  256. !                 !data[i].selfJoin && !data[j].selfJoin;
  257.           if (arcsJoin)
  258.               arc->render = 0;
  259.           else
  260. ***************
  261. *** 1074,1081 ****
  262.                   arc->join = arcs[prevphase].njoins;
  263.               }
  264.           } else {
  265.               if ((prevphase == 0 || isDoubleDash) &&
  266. !                 !data[i].selfJoin)
  267.               {
  268.                   addCap (&arcs[prevphase].caps, &arcs[prevphase].ncaps,
  269.                        &capSize[prevphase], LEFT_END, k);
  270. --- 1121,1132 ----
  271.                   arc->join = arcs[prevphase].njoins;
  272.               }
  273.           } else {
  274. +             /*
  275. +              * cap the left end of this arc
  276. +              * unless it joins itself
  277. +              */
  278.               if ((prevphase == 0 || isDoubleDash) &&
  279. !                 !arc->selfJoin)
  280.               {
  281.                   addCap (&arcs[prevphase].caps, &arcs[prevphase].ncaps,
  282.                        &capSize[prevphase], LEFT_END, k);
  283. ***************
  284. *** 1103,1110 ****
  285.                * hardly matters...
  286.                */
  287.               if ((iphase == 0 || isDoubleDash) &&
  288. !                 (nexti != start || arcsJoin && isDashed) &&
  289. !                  !data[j].selfJoin)
  290.                   addCap (&arcs[iphase].caps, &arcs[iphase].ncaps,
  291.                        &capSize[iphase], RIGHT_END, nextk);
  292.           }
  293. --- 1154,1160 ----
  294.                * hardly matters...
  295.                */
  296.               if ((iphase == 0 || isDoubleDash) &&
  297. !                 (nexti != start || arcsJoin && isDashed))
  298.                   addCap (&arcs[iphase].caps, &arcs[iphase].ncaps,
  299.                        &capSize[iphase], RIGHT_END, nextk);
  300.           }
  301. ***************
  302. *** 1288,1293 ****
  303. --- 1338,1348 ----
  304.       return a1;
  305.   }
  306.   
  307. + /*
  308. +  * To avoid inaccuracy at the cardinal points, use trig functions
  309. +  * which are exact for those angles
  310. +  */
  311. + 
  312.   # define Dsin(d)    ((d) == 0.0 ? 0.0 : ((d) == 90.0 ? 1.0 : sin(d*M_PI/180.0)))
  313.   # define Dcos(d)    ((d) == 0.0 ? 1.0 : ((d) == 90.0 ? 0.0 : cos(d*M_PI/180.0)))
  314.   
  315. ***************
  316. *** 1330,1338 ****
  317.   }
  318.   
  319.   /*
  320. !  * draw zero width/height arcs with the rectangle routines
  321.    */
  322.   
  323.   drawZeroArc (pDraw, pGC, tarc, left, right)
  324.       DrawablePtr   pDraw;
  325.       GCPtr         pGC;
  326. --- 1385,1403 ----
  327.   }
  328.   
  329.   /*
  330. !  * scan convert wide arcs.
  331.    */
  332.   
  333. + #undef fabs
  334. + #undef min
  335. + #undef max
  336. + 
  337. + extern double    ceil (), floor (), fabs (), sin (), cos (), sqrt (), pow ();
  338. + 
  339. + /*
  340. +  * draw zero width/height arcs
  341. +  */
  342. + 
  343.   drawZeroArc (pDraw, pGC, tarc, left, right)
  344.       DrawablePtr   pDraw;
  345.       GCPtr         pGC;
  346. ***************
  347. *** 1342,1348 ****
  348.       double    x0, y0, x1, y1, w, h;
  349.       int    a0, a1;
  350.       double    startAngle, endAngle;
  351. -     SppPointRec    box[4];
  352.       double    l;
  353.   
  354.       l = pGC->lineWidth;
  355. --- 1407,1412 ----
  356. ***************
  357. *** 1386,1401 ****
  358.           }
  359.       }
  360.       if (x1 != x0 && y1 != y0) {
  361. !         box[0].x = x0;
  362. !         box[0].y = y0;
  363. !         box[1].x = x1;
  364. !         box[1].y = y0;
  365. !         box[2].x = x1;
  366. !         box[2].y = y1;
  367. !         box[3].x = x0;
  368. !         box[3].y = y1;
  369. !         miFillSppPoly (pDraw, pGC, 4, box, tarc.x, tarc.y,
  370. !                    w, h);
  371.       }
  372.       if (right) {
  373.           if (h != 0) {
  374. --- 1450,1481 ----
  375.           }
  376.       }
  377.       if (x1 != x0 && y1 != y0) {
  378. !         int    minx, maxx, miny, maxy, y, t;
  379. !         xRectangle  rect;
  380. ! 
  381. !         minx = ceil (x0 + w) + tarc.x;
  382. !         maxx = ceil (x1 + w) + tarc.x;
  383. !         if (minx > maxx) {
  384. !             t = minx;
  385. !             minx = maxx;
  386. !             maxx = t;
  387. !         }
  388. !         miny = ceil (y0 + h) + tarc.y;
  389. !         maxy = ceil (y1 + h) + tarc.y;
  390. !         if (miny > maxy) {
  391. !             t = miny;
  392. !             miny = maxy;
  393. !             maxy = t;
  394. !         }
  395. !         rect.x = minx;
  396. !         rect.y = miny;
  397. !         rect.width = maxx - minx;
  398. !         rect.height = maxy - miny;
  399. !         (*pGC->PolyFillRect) (pDraw, pGC, 1, &rect);
  400. ! /*
  401. !         for (y = miny; y < maxy; y++)
  402. !             newFinalSpan (y, minx, maxx);
  403. ! */
  404.       }
  405.       if (right) {
  406.           if (h != 0) {
  407. ***************
  408. *** 1433,1449 ****
  409.       }
  410.   }
  411.   
  412. -  
  413. - /*
  414. -  * scan convert wide arcs.
  415. -  */
  416. - 
  417. - #undef fabs
  418. - #undef min
  419. - #undef max
  420. - 
  421. - extern double    ceil (), floor (), fabs (), sin (), cos (), sqrt (), pow ();
  422. - 
  423.   # define BINARY_LIMIT    (0.1)
  424.   # define NEWTON_LIMIT    (0.0000001)
  425.   
  426. --- 1513,1518 ----
  427. ***************
  428. *** 1512,1530 ****
  429.       return a < b ? a : b;
  430.   }
  431.   
  432. ! boundedLt (value, bounds)
  433. ! double    value;
  434. ! struct bound    bounds;
  435. ! {
  436. !     return bounds.min <= value && value < bounds.max;
  437. ! }
  438.   
  439. ! boundedLe (value, bounds)
  440. ! double    value;
  441. ! struct bound    bounds;
  442. ! {
  443. !     return bounds.min <= value && value <= bounds.max;
  444. ! }
  445.   
  446.   /*
  447.    * this computes the elipse y value associated with the
  448. --- 1581,1591 ----
  449.       return a < b ? a : b;
  450.   }
  451.   
  452. ! #define boundedLt(value, bounds) \
  453. !     ((bounds).min <= (value) && (value) < (bounds).max)
  454.   
  455. ! #define boundedLe(value, bounds)\
  456. !     ((bounds).min <= (value) && (value) <= (bounds).max)
  457.   
  458.   /*
  459.    * this computes the elipse y value associated with the
  460. ***************
  461. *** 1673,1678 ****
  462. --- 1734,1745 ----
  463.       return line->m * y + line->b;
  464.   }
  465.   
  466. + /*
  467. +  * compute various accelerators for an elipse.  These
  468. +  * are simply values that are used repeatedly in
  469. +  * the computations
  470. +  */
  471. + 
  472.   computeAcc (def, acc)
  473.       struct arc_def        *def;
  474.       struct accelerators    *acc;
  475. ***************
  476. *** 1687,1692 ****
  477. --- 1754,1764 ----
  478.       acc->tail_y = tailElipseY (def->w, def->h, def->l);
  479.   }
  480.           
  481. + /*
  482. +  * compute y value bounds of various portions of the arc,
  483. +  * the outer edge, the elipse and the inner edge.
  484. +  */
  485. + 
  486.   computeBound (def, bound, acc, right, left)
  487.       struct arc_def        *def;
  488.       struct arc_bound    *bound;
  489. ***************
  490. *** 1721,1727 ****
  491.       
  492.       /*
  493.        * save the line end points for the
  494. !      * cap code to use
  495.        */
  496.   
  497.       if (right) {
  498. --- 1793,1802 ----
  499.       
  500.       /*
  501.        * save the line end points for the
  502. !      * cap code to use.  Careful here, these are
  503. !      * in cartesean coordinates (y increasing upwards)
  504. !      * while the cap code uses inverted coordinates
  505. !      * (y increasing downwards)
  506.        */
  507.   
  508.       if (right) {
  509. ***************
  510. *** 1772,1778 ****
  511.   /*
  512.    * using newtons method and a binary search, compute the elipse y value
  513.    * associated with the given edge value (either outer or
  514. !  * inner)
  515.    */
  516.   
  517.   double
  518. --- 1847,1881 ----
  519.   /*
  520.    * using newtons method and a binary search, compute the elipse y value
  521.    * associated with the given edge value (either outer or
  522. !  * inner).  This is the heart of the scan conversion code and
  523. !  * is generally called three times for each span.  It should
  524. !  * be optimized further.
  525. !  *
  526. !  * the general idea here is to solve the equation:
  527. !  *
  528. !  *                               w^2 * l
  529. !  *   edge_y = y + y * -------------------------------
  530. !  *                    2 * sqrt (x^2 * h^4 + y^2 * w^4)
  531. !  *
  532. !  * for y.  (x, y) is a point on the elipse, so x can be
  533. !  * found from y:
  534. !  *
  535. !  *                ( h^2 - y^2 )
  536. !  *   x = w * sqrt ( --------- )
  537. !  *                (    h^2    )
  538. !  *
  539. !  * The information given at the start of the search
  540. !  * is two points which are known to bound the desired
  541. !  * solution, a binary search starts with these two points
  542. !  * and converges close to a solution, which is then
  543. !  * refined with newtons method.  Newtons method
  544. !  * cannot be used in isolation as it does not always
  545. !  * converge to the desired solution without a close
  546. !  * starting point, the binary search simply provides
  547. !  * that point.  Increasing the solution interval for
  548. !  * the binary search will certainly speed up the
  549. !  * solution, but may generate a range which causes
  550. !  * the newtons method to fail.  This needs study.
  551.    */
  552.   
  553.   double
  554. ***************
  555. *** 1781,1794 ****
  556.       struct arc_def        *def;
  557.       struct arc_bound    *bound;
  558.       struct accelerators    *acc;
  559. !     double            y0, y1;
  560.   {
  561. !     double    w, h, l, h2, h4, w2, w4, x, y2;
  562. !     double    newtony, binaryy;
  563. !     double    value0, value1, valuealt;
  564. !     double    newtonvalue, binaryvalue;
  565. !     double    minY, maxY;
  566. !     double    (*f)();
  567.       
  568.       /*
  569.        * compute some accelerators
  570. --- 1884,1898 ----
  571.       struct arc_def        *def;
  572.       struct arc_bound    *bound;
  573.       struct accelerators    *acc;
  574. !     register double        y0, y1;
  575.   {
  576. !     register double    w, h, l, h2, h4, w2, w4, x, y2;
  577. !     double        newtony, binaryy;
  578. !     double        value0, value1, valuealt;
  579. !     double        newtonvalue, binaryvalue;
  580. !     double        minY, maxY;
  581. !     double        binarylimit;
  582. !     double        (*f)();
  583.       
  584.       /*
  585.        * compute some accelerators
  586. ***************
  587. *** 1816,1821 ****
  588. --- 1920,1928 ----
  589.           return y1;
  590.       if (value1 > 0 == value0 > 0)
  591.           return -1.0;    /* an illegal value */
  592. +     binarylimit = fabs ((value1 - value0) / 25.0);
  593. +     if (binarylimit < BINARY_LIMIT)
  594. +         binarylimit = BINARY_LIMIT;
  595.       /*
  596.        * binary search for a while
  597.        */
  598. ***************
  599. *** 1834,1841 ****
  600.           binaryvalue = ( binaryy + (binaryy * w2 * l) /
  601.                     (2 * Sqrt (x*x * h4 + y2 * w4))) - edge_y;
  602.   
  603. -         if (binaryvalue == 0)
  604. -             return binaryy;
  605.           if (binaryvalue > 0 == value0 > 0) {
  606.               y0 = binaryy;
  607.               value0 = binaryvalue;
  608. --- 1941,1946 ----
  609. ***************
  610. *** 1843,1849 ****
  611.               y1 = binaryy;
  612.               value1 = binaryvalue;
  613.           }
  614. !     } while (fabs (value1) > BINARY_LIMIT);
  615.   
  616.       /*
  617.        * clean up the estimate with newtons method
  618. --- 1948,1956 ----
  619.               y1 = binaryy;
  620.               value1 = binaryvalue;
  621.           }
  622. !     } while (fabs (value1) > binarylimit);
  623. !     if (binaryvalue == 0)
  624. !         return binaryy;
  625.   
  626.       /*
  627.        * clean up the estimate with newtons method
  628. ***************
  629. *** 1889,1901 ****
  630.   
  631.   double
  632.   outerX (outer_y, def, bound, acc)
  633. !     double            outer_y;
  634. !     struct arc_def        *def;
  635.       struct arc_bound    *bound;
  636.       struct accelerators    *acc;
  637.   {
  638.       double    y;
  639.   
  640.       if (outer_y == bound->outer.min)
  641.           y = bound->elipse.min;
  642.       if (outer_y == bound->outer.max)
  643. --- 1996,2018 ----
  644.   
  645.   double
  646.   outerX (outer_y, def, bound, acc)
  647. !     register double        outer_y;
  648. !     register struct arc_def    *def;
  649.       struct arc_bound    *bound;
  650.       struct accelerators    *acc;
  651.   {
  652.       double    y;
  653.   
  654. +     /*
  655. +      * special case for circles
  656. +      */
  657. +     if (def->w == def->h) {
  658. +         register double    x;
  659. + 
  660. +         x = def->w + def->l/2.0;
  661. +         x = Sqrt (x * x - outer_y * outer_y);
  662. +         return x;
  663. +     }
  664.       if (outer_y == bound->outer.min)
  665.           y = bound->elipse.min;
  666.       if (outer_y == bound->outer.max)
  667. ***************
  668. *** 1902,1908 ****
  669.           y = bound->elipse.max;
  670.       else
  671.           y = elipseY (outer_y, def, bound, acc, 1,
  672. !                   bound->elipse.min, bound->elipse.max, -1.0);
  673.       return outerXfromY (y, def, acc);
  674.   }
  675.   
  676. --- 2019,2025 ----
  677.           y = bound->elipse.max;
  678.       else
  679.           y = elipseY (outer_y, def, bound, acc, 1,
  680. !                   bound->elipse.min, bound->elipse.max);
  681.       return outerXfromY (y, def, acc);
  682.   }
  683.   
  684. ***************
  685. *** 1911,1924 ****
  686.    */
  687.   
  688.   innerXs (inner_y, def, bound, acc, innerX1p, innerX2p)
  689. !     double            inner_y;
  690.       struct arc_def        *def;
  691.       struct arc_bound    *bound;
  692.       struct accelerators    *acc;
  693.       double            *innerX1p, *innerX2p;
  694.   {
  695. !     double    x1, x2, xalt, y0, y1, altY, elipse_y1, elipse_y2;
  696.   
  697.       if (boundedLe (acc->tail_y, bound->elipse)) {
  698.           if (def->h > def->w) {
  699.               y0 = bound->elipse.min;
  700. --- 2028,2053 ----
  701.    */
  702.   
  703.   innerXs (inner_y, def, bound, acc, innerX1p, innerX2p)
  704. !     register double        inner_y;
  705.       struct arc_def        *def;
  706.       struct arc_bound    *bound;
  707.       struct accelerators    *acc;
  708.       double            *innerX1p, *innerX2p;
  709.   {
  710. !     register double    x1, x2;
  711. !     double        xalt, y0, y1, altY, elipse_y1, elipse_y2;
  712.   
  713. +     /*
  714. +      * special case for circles
  715. +      */
  716. +     if (def->w == def->h) {
  717. +         x1 = def->w - def->l/2.0;
  718. +         x2 = Sqrt (x1 * x1 - inner_y * inner_y);
  719. +         if (x1 < 0)
  720. +             x2 = -x2;
  721. +         *innerX1p = *innerX2p = x2;
  722. +         return;
  723. +     }
  724.       if (boundedLe (acc->tail_y, bound->elipse)) {
  725.           if (def->h > def->w) {
  726.               y0 = bound->elipse.min;
  727. ***************
  728. *** 2048,2068 ****
  729.       double    elipse_y, elipse_x, x, xalt;
  730.       double    maxMin;
  731.   
  732. !     elipse_y = hookElipseY (scan_y, def, bound, acc, left);
  733. !     if (boundedLe (elipse_y, bound->elipse)) {
  734. !         /*
  735. !          * compute the value of the second
  736. !          * derivative
  737. !          */
  738. !         maxMin = elipse_y*elipse_y*elipse_y * acc->h2mw2 -
  739. !          acc->h2 * scan_y * (3 * elipse_y*elipse_y - 2*acc->h2);
  740. !         if ((left && maxMin > 0) || (!left && maxMin < 0)) {
  741. !             if (elipse_y == 0)
  742. !                 return def->w + left ? -def->l/2 : def->l/2;
  743. !             x = (acc->h2 * scan_y - elipse_y * acc->h2mw2) *
  744. !                 Sqrt (acc->h2 - elipse_y * elipse_y) /
  745. !                  (def->h * def->w * elipse_y);
  746. !             return x;
  747.           }
  748.       }
  749.       if (left) {
  750. --- 2177,2199 ----
  751.       double    elipse_y, elipse_x, x, xalt;
  752.       double    maxMin;
  753.   
  754. !     if (def->w != def->h) {
  755. !         elipse_y = hookElipseY (scan_y, def, bound, acc, left);
  756. !         if (boundedLe (elipse_y, bound->elipse)) {
  757. !             /*
  758. !               * compute the value of the second
  759. !               * derivative
  760. !               */
  761. !             maxMin = elipse_y*elipse_y*elipse_y * acc->h2mw2 -
  762. !               acc->h2 * scan_y * (3 * elipse_y*elipse_y - 2*acc->h2);
  763. !             if ((left && maxMin > 0) || (!left && maxMin < 0)) {
  764. !                 if (elipse_y == 0)
  765. !                     return def->w + left ? -def->l/2 : def->l/2;
  766. !                 x = (acc->h2 * scan_y - elipse_y * acc->h2mw2) *
  767. !                     Sqrt (acc->h2 - elipse_y * elipse_y) /
  768. !                      (def->h * def->w * elipse_y);
  769. !                 return x;
  770. !             }
  771.           }
  772.       }
  773.       if (left) {
  774. ***************
  775. *** 2087,2092 ****
  776. --- 2218,2228 ----
  777.       return x;
  778.   }
  779.   
  780. + /*
  781. +  * generate the set of spans with
  782. +  * the given y coordinate
  783. +  */
  784. + 
  785.   arcSpan (y, def, bounds, acc)
  786.       double            y;
  787.       struct arc_def        *def;
  788. ***************
  789. *** 2159,2174 ****
  790.       int            min, max;    /* x values */
  791.   };
  792.   
  793.   fillSpans (pDrawable, pGC)
  794.       DrawablePtr    pDrawable;
  795.       GCPtr    pGC;
  796.   {
  797. !     struct finalSpan    **f;
  798. !     struct finalSpan    *span, *nextspan;
  799. !     DDXPointPtr        xSpans, xSpan;
  800. !     int            *xWidths, *xWidth;
  801. !     int            i;
  802. !     int            spany;
  803.   
  804.       if (nspans == 0)
  805.           return;
  806. --- 2295,2365 ----
  807.       int            min, max;    /* x values */
  808.   };
  809.   
  810. + static struct finalSpan    *freeFinalSpans, *tmpFinalSpan;
  811. + 
  812. + # define allocFinalSpan()   (freeFinalSpans ?\
  813. +                 ((tmpFinalSpan = freeFinalSpans), \
  814. +                  (freeFinalSpans = freeFinalSpans->next), \
  815. +                  (tmpFinalSpan->next = 0), \
  816. +                  tmpFinalSpan) : \
  817. +                  realAllocSpan ())
  818. + 
  819. + # define SPAN_CHUNK_SIZE    128
  820. + 
  821. + struct finalSpanChunk {
  822. +     struct finalSpan    data[SPAN_CHUNK_SIZE];
  823. +     struct finalSpanChunk    *next;
  824. + };
  825. + 
  826. + static struct finalSpanChunk    *chunks;
  827. + 
  828. + struct finalSpan *
  829. + realAllocSpan ()
  830. + {
  831. +     register struct finalSpanChunk    *newChunk;
  832. +     register struct finalSpan    *span;
  833. +     register int            i;
  834. + 
  835. +     newChunk = (struct finalSpanChunk *) Xalloc (sizeof (struct finalSpanChunk));
  836. +     if (!newChunk)
  837. +         return (struct finalSpan *) Xalloc (sizeof (struct finalSpan));
  838. +     newChunk->next = chunks;
  839. +     chunks = newChunk;
  840. +     freeFinalSpans = span = newChunk->data + 1;
  841. +     for (i = 1; i < SPAN_CHUNK_SIZE-1; i++) {
  842. +         span->next = span+1;
  843. +         span++;
  844. +     }
  845. +     span->next = 0;
  846. +     span = newChunk->data;
  847. +     span->next = 0;
  848. +     return span;
  849. + }
  850. + 
  851. + disposeFinalSpans ()
  852. + {
  853. +     struct finalSpanChunk    *chunk, *next;
  854. + 
  855. +     for (chunk = chunks; chunk; chunk = next) {
  856. +         next = chunk->next;
  857. +         Xfree (chunk);
  858. +     }
  859. +     chunks = 0;
  860. +     freeFinalSpans = 0;
  861. + }
  862. + 
  863.   fillSpans (pDrawable, pGC)
  864.       DrawablePtr    pDrawable;
  865.       GCPtr    pGC;
  866.   {
  867. !     register struct finalSpan    *span;
  868. !     register DDXPointPtr        xSpan;
  869. !     register int            *xWidth;
  870. !     register int            i;
  871. !     register struct finalSpan    **f;
  872. !     register int            spany;
  873. !     DDXPointPtr            xSpans;
  874. !     int                *xWidths;
  875.   
  876.       if (nspans == 0)
  877.           return;
  878. ***************
  879. *** 2177,2194 ****
  880.       i = 0;
  881.       f = finalSpans;
  882.       for (spany = finalMiny; spany < finalMaxy; spany++, f++) {
  883. !         for (span = *f; span; span=nextspan) {
  884. !             nextspan = span->next;
  885. !             if (span->max > span->min) {
  886. !                 xSpan->x = span->min;
  887. !                 xSpan->y = spany;
  888. !                 ++xSpan;
  889. !                 *xWidth++ = span->max - span->min;
  890. !                 ++i;
  891.               }
  892. !             Xfree (span);
  893.           }
  894.       }
  895.       Xfree (finalSpans);
  896.       (*pGC->FillSpans) (pDrawable, pGC, i, xSpans, xWidths, TRUE);
  897.       Xfree (xSpans);
  898. --- 2368,2386 ----
  899.       i = 0;
  900.       f = finalSpans;
  901.       for (spany = finalMiny; spany < finalMaxy; spany++, f++) {
  902. !         for (span = *f; span; span=span->next) {
  903. !             if (span->max <= span->min) {
  904. !                 printf ("span width: %d\n", span->max-span->min);
  905. !                 continue;
  906.               }
  907. !             xSpan->x = span->min;
  908. !             xSpan->y = spany;
  909. !             ++xSpan;
  910. !             *xWidth++ = span->max - span->min;
  911. !             ++i;
  912.           }
  913.       }
  914. +     disposeFinalSpans ();
  915.       Xfree (finalSpans);
  916.       (*pGC->FillSpans) (pDrawable, pGC, i, xSpans, xWidths, TRUE);
  917.       Xfree (xSpans);
  918. ***************
  919. *** 2200,2214 ****
  920.       nspans = 0;
  921.   }
  922.   
  923. ! # define SPAN_REALLOC    2048
  924.   
  925.   struct finalSpan **
  926. ! findSpan (y)
  927.   {
  928.       struct finalSpan    **newSpans;
  929.       int            newSize, newMiny, newMaxy;
  930. -     int            i;
  931.       int            change;
  932.   
  933.       if (y < finalMiny || y >= finalMaxy) {
  934.           if (y < finalMiny)
  935. --- 2392,2410 ----
  936.       nspans = 0;
  937.   }
  938.   
  939. ! # define SPAN_REALLOC    1024
  940.   
  941. + # define findSpan(y) ((finalMiny <= (y) && (y) < finalMaxy) ? \
  942. +               &finalSpans[(y) - finalMiny] : \
  943. +               realFindSpan (y))
  944. + 
  945.   struct finalSpan **
  946. ! realFindSpan (y)
  947.   {
  948.       struct finalSpan    **newSpans;
  949.       int            newSize, newMiny, newMaxy;
  950.       int            change;
  951. +     int            i;
  952.   
  953.       if (y < finalMiny || y >= finalMaxy) {
  954.           if (y < finalMiny)
  955. ***************
  956. *** 2234,2243 ****
  957.                      finalSize * sizeof (struct finalSpan *));
  958.               Xfree (finalSpans);
  959.           }
  960. !         for (i = newMiny; i < finalMiny; i++)
  961. !             newSpans[i-newMiny] = 0;
  962. !         for (i = finalMaxy; i < newMaxy; i++)
  963. !             newSpans[i-newMiny] = 0;
  964.           finalSpans = newSpans;
  965.           finalMaxy = newMaxy;
  966.           finalMiny = newMiny;
  967. --- 2430,2440 ----
  968.                      finalSize * sizeof (struct finalSpan *));
  969.               Xfree (finalSpans);
  970.           }
  971. !         if ((i = finalMiny - newMiny) > 0)
  972. !             bzero (newSpans, i * sizeof (struct finalSpan *));
  973. !         if ((i = newMaxy - finalMaxy) > 0)
  974. !             bzero (newSpans + finalMaxy - newMiny,
  975. !                    i * sizeof (struct finalSpan *));
  976.           finalSpans = newSpans;
  977.           finalMaxy = newMaxy;
  978.           finalMiny = newMiny;
  979. ***************
  980. *** 2247,2255 ****
  981.   }
  982.   
  983.   newFinalSpan (y, xmin, xmax)
  984.   {
  985. !     struct finalSpan    **f;
  986. !     struct finalSpan    *x, *oldx, *prev;
  987.   
  988.       f = findSpan (y);
  989.       oldx = 0;
  990. --- 2444,2456 ----
  991.   }
  992.   
  993.   newFinalSpan (y, xmin, xmax)
  994. + int        y;
  995. + register int    xmin, xmax;
  996.   {
  997. !     register struct finalSpan    *x;
  998. !     register struct finalSpan    **f;
  999. !     struct finalSpan        *oldx;
  1000. !     struct finalSpan        *prev;
  1001.   
  1002.       f = findSpan (y);
  1003.       oldx = 0;
  1004. ***************
  1005. *** 2269,2275 ****
  1006.                       else
  1007.                           *f = x->next;
  1008.                       --nspans;
  1009. -                     Xfree (x);
  1010.                   } else {
  1011.                       x->min = min (x->min, xmin);
  1012.                       x->max = max (x->max, xmax);
  1013. --- 2470,2475 ----
  1014. ***************
  1015. *** 2285,2291 ****
  1016.               break;
  1017.       }
  1018.       if (!oldx) {
  1019. !         x = (struct finalSpan *) Xalloc (sizeof (struct finalSpan));
  1020.           x->min = xmin;
  1021.           x->max = xmax;
  1022.           x->next = *f;
  1023. --- 2485,2491 ----
  1024.               break;
  1025.       }
  1026.       if (!oldx) {
  1027. !         x = allocFinalSpan ();
  1028.           x->min = xmin;
  1029.           x->max = xmax;
  1030.           x->next = *f;
  1031. ***************
  1032. *** 2318,2371 ****
  1033.       sppPoint->y = -sppPoint->y;
  1034.   }
  1035.   
  1036. ! mirrorSpan (quadrant, y, min, max)
  1037. !     double        y;
  1038. !     double        min, max;
  1039. ! {
  1040. !     int        spany, xmin, xmax;
  1041. !     double        t;
  1042.   
  1043. -     switch (quadrant) {
  1044. -     case 0:
  1045. -         break;
  1046. -     case 1:
  1047. -         t = -max;
  1048. -         max = -min;
  1049. -         min = t;
  1050. -         break;
  1051. -     case 2:
  1052. -         t = -max;
  1053. -         max = -min;
  1054. -         min = t;
  1055. -         y = -y;
  1056. -         break;
  1057. -     case 3:
  1058. -         y = -y;
  1059. -         break;
  1060. -     }
  1061. -     xmin = (int) ceil (min + arcXcenter) + arcXoffset;
  1062. -     xmax = (int) ceil (max + arcXcenter) + arcXoffset;
  1063. -     spany = (int) (ceil (arcYcenter - y)) + arcYoffset;
  1064. -     if (xmax > xmin)
  1065. -         newFinalSpan (spany, xmin, xmax);
  1066. - }
  1067. - 
  1068.   static int    quadrantMask;
  1069.   
  1070. ! mergeSpan (y, min, max)
  1071. !     double    y, min, max;
  1072.   {
  1073. !     if (quadrantMask & 1)
  1074. !         mirrorSpan (0, y, min, max);
  1075. !     if (quadrantMask & 2)
  1076. !         mirrorSpan (1, y, min, max);
  1077. !     if (quadrantMask & 4)
  1078. !         mirrorSpan (2, y, min, max);
  1079. !     if (quadrantMask & 8)
  1080. !         mirrorSpan (3, y, min, max);
  1081.   }
  1082.   
  1083. ! static double    spanY;
  1084.   
  1085.   drawArc (x0, y0, w, h, l, a0, a1, right, left)
  1086.       int    x0, y0, w, h, l, a0, a1;
  1087. --- 2518,2577 ----
  1088.       sppPoint->y = -sppPoint->y;
  1089.   }
  1090.   
  1091. ! static double    spanY;
  1092.   
  1093.   static int    quadrantMask;
  1094.   
  1095. ! span (left, right)
  1096. !     double    left, right;
  1097.   {
  1098. !     register int    mask = quadrantMask, bit;
  1099. !     register double    min, max, y;
  1100. !     int    xmin, xmax, spany;
  1101. ! 
  1102. !     while (mask) {
  1103. !         bit = lowbit (mask);
  1104. !         mask &= ~bit;
  1105. !         switch (bit) {
  1106. !         case 1:
  1107. !             min = left;
  1108. !             max = right;
  1109. !             y = spanY;
  1110. !             break;
  1111. !         case 2:
  1112. !             min = -right;
  1113. !             max = -left;
  1114. !             y = spanY;
  1115. !             break;
  1116. !         case 4:
  1117. !             min = -right;
  1118. !             max = -left;
  1119. !             y = -spanY;
  1120. !             break;
  1121. !         case 8:
  1122. !             min = left;
  1123. !             max = right;
  1124. !             y = -spanY;
  1125. !             break;
  1126. !         default:
  1127. !             abort ();
  1128. !         }
  1129. !         xmin = (int) ceil (min + arcXcenter) + arcXoffset;
  1130. !         xmax = (int) ceil (max + arcXcenter) + arcXoffset;
  1131. !         spany = (int) (ceil (arcYcenter - y)) + arcYoffset;
  1132. ! 
  1133. !         if (xmax > xmin)
  1134. !             newFinalSpan (spany, xmin, xmax);
  1135. !     }
  1136.   }
  1137.   
  1138. ! /*
  1139. !  * split an arc into pieces which are scan-converted
  1140. !  * in the first-quadrant and mirrored into position.
  1141. !  * This is necessary as the scan-conversion code can
  1142. !  * only deal with arcs completely contained in the
  1143. !  * first quadrant.
  1144. !  */
  1145.   
  1146.   drawArc (x0, y0, w, h, l, a0, a1, right, left)
  1147.       int    x0, y0, w, h, l, a0, a1;
  1148. ***************
  1149. *** 2555,2560 ****
  1150. --- 2761,2770 ----
  1151.           drawQuadrant (&def, &acc, sweep[j].a0, sweep[j].a1, mask, 
  1152.                      passRight, passLeft);
  1153.       }
  1154. +     /*
  1155. +      * mirror the coordinates generated for the
  1156. +      * faces of the arc
  1157. +      */
  1158.       if (right) {
  1159.           mirrorSppPoint (rightq, &right->clock);
  1160.           mirrorSppPoint (rightq, &right->center);
  1161. ***************
  1162. *** 2611,2618 ****
  1163.       /*
  1164.        * add the pixel at the top of the arc
  1165.        */
  1166. !     if (a1 == 90 * 64 && (quadrantMask & 1) && ((int) (def->w * 2 + def->l)) & 1)
  1167. !         mirrorSpan (0, def->h + def->l/2, 0.0, 1.0);
  1168.   }
  1169.   
  1170.   max (x, y)
  1171. --- 2821,2831 ----
  1172.       /*
  1173.        * add the pixel at the top of the arc
  1174.        */
  1175. !     if (a1 == 90 * 64 && (mask & 1) && ((int) (def->w * 2 + def->l)) & 1) {
  1176. !         quadrantMask = 1;
  1177. !         spanY = def->h + def->l/2;
  1178. !         span (0.0, 1.0);
  1179. !     }
  1180.   }
  1181.   
  1182.   max (x, y)
  1183. ***************
  1184. *** 2625,2632 ****
  1185.       return x<y? x:y;
  1186.   }
  1187.   
  1188. - span (left, right)
  1189. - double    left, right;
  1190. - {
  1191. -     mergeSpan (spanY, left, right);
  1192. - }
  1193. --- 2838,2840 ----
  1194. -- 
  1195. Mike Wexler(wyse!mikew)    Phone: (408)433-1000 x1330
  1196. Moderator of comp.sources.x
  1197.